package com.dataStructure.并查集;

/**
 * 虽然有了基于rank的优化，树会相对平衡一点
 * 但是随着Union次数的增多，树的高度依然会越来越高
 * 导致find操作变慢，尤其是底层节点（因为find是不断向上找到根节点）
 *
 * 什么是路径压缩？
 * 在find时使路径上的所有节点都指向根节点，从而降低树的高度
 *
 *      即 Quick Union - 基于rank的优化 - 路径压缩
 *
 * 路径压缩使路径上的所有节点都指向根节点，所以实现成本稍高
 */

@SuppressWarnings("all")
public class 并查集_QuickUnion_路径压缩优化 extends 并查集_QuickUnion_Rank优化{

    public 并查集_QuickUnion_路径压缩优化(int capacity) {
        super(capacity);
    }

    @Override
    public int find(int v) {
        rangCheck(v);
       /* while (v != parents[v]){
            v = parents[v];
        }
        return v;*/

        //如果v的父节点不是他本身，即没有找到根节点
        if (parents[v] != v) {
            //递归的调用find方法直到找到根节点，并且会在find时使路径上的所有节点都指向根节点
            parents[v] = find(parents[v]);
        }
        return parents[v];
    }
}
